package pub.dsb.example.algorithm;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * <p>
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
 * </p>
 *
 * @author Yi
 * @version V1.0.0
 * @date 2021/1/4 16:21
 * @modificationHistory=========================逻辑或功能性重大变更记录
 * @modify By: {修改人} 2021/1/4 16:21
 * @modify reason: {方法名}:{原因}
 * ...
 * @since V1.0.0
 */
public class LC3Test {
    public static void main(String[] args) {
        System.out.println(new Solution20200103().lengthOfLongestSubstring("abcabcdbb"));
    }
}

class Solution20200103 {
    public int lengthOfLongestSubstring(String s) {
        /**
         以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb;
         以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb;
         以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb;
         以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb;
         以 abca(b)cbb 开始的最长字符串为 abca(bc)bb;
         以 abcab(c)bb 开始的最长字符串为 abcab(cb)b;
         以 abcabc(b)b 开始的最长字符串为 abcabc(b)b;
         以 abcabcb(b) 开始的最长字符串为 abcabcb(b);
         */
        Set<Character> characterSet = new HashSet<>();
        int rs = -1, ans = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i != 0) {
                //左指针向右移动一位，移除前一位重复字符
                characterSet.remove(s.charAt(i-1));
            }
            while (rs < s.length() - 1 && !characterSet.contains(s.charAt(rs+1))) {
                // 循环向后遍历,直到遇到不同的字符
                characterSet.add(s.charAt(rs+1));
                ++rs;
            }
            ans = Math.max(ans, rs + 1-i);
        }
        return ans;
    }
}